﻿/* 8. Write a program that finds the sequence of maximal sum in given array. 
 * Example: {2, 3, -6, -1, 2, -1, 6, 4, -8, 8} -> {2, -1, 6, 4} */

using System;

public class SequenceWithMaxSum
{
    #region Variables
    public static int n;
    public static double[] array;

    public static int stoneMaxLeft = 0;
    public static int stoneMaxRight = 0;
    public static double stoneMaxSum = 0;

    public static double? maxNonpositive = null;
    public static int? countMaxNonpositives = 0;
    public static bool noPositive = true;

    public static int maxLeft = 0;
    public static int maxRight = 0;
    public static double maxSum = 0;

    public static int left;
    public static int right;
    public static double sum = 0;

    public static bool findingNewPositive = false;
    #endregion

    public static void Main()
    {
        if (0 < InputN())
        {
            array = new double[n];

            for (int index = 0; index < n; index++)
            {
                InputMemberOfArray(index);

                if (noPositive)
                    StillNoPositive(index);
                else if (findingNewPositive == false)
                    ExpandingSequence(index);
                else
                    FindingNewPositive(index);
            }

            PrintSequenceWithMaxSum();
        }
        else
            Console.WriteLine("The length of array must be natural!\n");
    }

    public static int InputN()
    {
        Console.Write("\nThe length of array: ");
        n = int.Parse(Console.ReadLine());
        Console.WriteLine();

        return n;
    }

    public static void InputMemberOfArray(int index)
    {
        Console.Write("Array[{0}] = ", index);
        array[index] = double.Parse(Console.ReadLine());
    }

    public static void ExpandingSequence(int index)
    {
        if (0 <= array[index])
        {
            right = index;
            sum += array[index];

            if (maxSum <= sum)
            {
                maxRight = index;
                maxSum += array[index];
            }

            if (stoneMaxSum <= maxSum)
            {
                stoneMaxLeft = maxLeft;
                stoneMaxRight = maxRight;
                stoneMaxSum = maxSum;
            }
        }
        else if (-array[index] <= sum)
        {
            right = index;
            sum += array[index];
        }
        else
        {
            stoneMaxLeft = maxLeft;
            stoneMaxRight = maxRight;
            stoneMaxSum = maxSum;

            findingNewPositive = true;
        }
    }

    public static void FindingNewPositive(int index)
    {
        if (0 < array[index])
        {
            findingNewPositive = false;

            maxLeft = index;
            maxRight = index;
            maxSum = array[index];

            left = index;
            right = index;
            sum = array[index];
        }
    }

    public static void StillNoPositive(int index)
    {
        if (0 < array[index])
        {
            noPositive = false;

            maxNonpositive = null;
            countMaxNonpositives = null;

            stoneMaxLeft = index;
            stoneMaxRight = index;
            stoneMaxSum = array[index];

            maxLeft = index;
            maxRight = index;
            maxSum = array[index];

            left = index;
            right = index;
            sum = array[index];
        }
        else
        {
            if ((maxNonpositive == null) || (maxNonpositive < array[index]))
            {
                maxNonpositive = array[index];
                countMaxNonpositives = 1;
            }
            else if (maxNonpositive == array[index])
            {
                if (countMaxNonpositives != null)
                    countMaxNonpositives++;
            }
        }
    }

    public static void PrintSequenceWithMaxSum()
    {
        if (maxNonpositive != null)
        {
            if (1 < countMaxNonpositives)
                Console.WriteLine("\nAll {0} sequences with maximal sum\nare eqivalent of this {1} {2} {3}\n",
                    countMaxNonpositives, "{", maxNonpositive, "}");
            else
                Console.WriteLine("\nThe unique sequence with maximal sum is: {0} {1} {2}\n",
                    "{", maxNonpositive, "}");
        }
        else
        {
            Console.Write("\nOne of the sequences with maximal sum is\n {0} {1}", "{", array[stoneMaxLeft]);
            for (int i = stoneMaxLeft + 1; i <= stoneMaxRight; i++)
                Console.Write(", {0}", array[i]);

            Console.WriteLine(" {0}\n", "}");
        }
    }
}